package sword_offer;

import java.util.Arrays;

/**
 * @author Synhard
 * @version 1.0
 * @Class sword_offer.Code22
 * @Description 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-16 9:43
 */
public class Code22 {
    public static void main(String[] args) {
//        int[] arr = new int[] {1,2,3,4,5,6,7};
        int[] arr = new int[] {1, 3, 5};
        System.out.println(Arrays.toString(exchange(arr)));
    }

//    public static int[] exchange(int[] nums) { // 冒泡排序会超时
//        int temp;
//        boolean change;
//        for (int i = 0; i < nums.length - 1; i++) { // 进行n - 1轮冒泡
//            change = false;
//            for (int j = 0; j < nums.length - i - 1; j++) {
//                if ((nums[j] & 1) == 0 && (nums[j + 1] & 1) ==1) {
//                    temp = nums[j];
//                    nums[j] = nums[j + 1];
//                    nums[j + 1] = temp;
//                    change = true;
//                }
//            }
//            if (!change)
//                break;
//        }
//        return nums;
//    }

    public static int[] exchange(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        int temp;
        while(low < high) {
            while ((arr[low] & 1) == 1 && low < high) {
                low++;
            }
            while ((arr[high] & 1) == 0 && low < high) {
                high--;
            }

                temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
                low++;
                high--;

        }
        return arr;
    }

}
/*
类似于冒泡排序,奇数向前交换
但是冒泡排序会超时，即使加了条件
使用双指针法，类似于快速排序。
 */